package com.gjx.leetcode;

//53. 最大子序和
//
//给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//
//示例:
//
//输入: [-2,1,-3,4,-1,2,1,-5,4],
//输出: 6
//解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
//进阶:
//
//如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。



public class Solution053 {
	public int maxSubArray(int[] nums) {
        
		if (nums == null || nums.length == 0) {
			return 0;
		}
		
		int max = Integer.MIN_VALUE;
		
		int sum = 0;
		
		for (int i=0; i<nums.length; i++) {
			
			max = Math.max(max, nums[i]);
			
			if (sum + nums[i] < 0) {
				sum = 0;
			} else {
				sum += nums[i];
				max = Math.max(max, sum);
			}
			
		}
		
		return max;
    }
	
	public int maxSubArrayNLgN(int[] nums) {
		if (nums == null || nums.length == 0) {
			return 0;
		}
		
		return help(nums, 0, nums.length-1);
	}
	
	private int help(int[] nums, int left, int right) {
		
		if (left > right) {
			return Integer.MIN_VALUE;
		}
		
		int mid = left + (right - left) / 2;
		
		
		int leftMax = 0;
		int leftSum = 0;
		int rightMax = 0;
		int rightSum = 0;
		
		for (int i=mid-1; i>=0; i--) {
			leftSum += nums[i];
			leftMax = Math.max(leftMax, leftSum);
		}
		
		for (int i=mid+1; i<nums.length; i++) {
			rightSum += nums[i];
			rightMax = Math.max(rightMax, rightSum);
		}
		
		int max = nums[mid] + leftMax + rightMax;
		
		return Math.max(max, Math.max(help(nums, left, mid-1), help(nums, mid+1, right)));
	}
	
	
	
	
	
	public static void main(String[] args) {
		new Solution053().maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4});
	}
}
